Abstract: Motivated by cryptography, quantum information theory, circuit complexity, and derandomization, there has been significant recent progress in the study of random permutations resembling a completely random permutation of n-bit strings. Of particular interest is the case where the measure of "resemblance" is approximation of the k-th moments of the matrix representations. Such random permutations are known as approximate k-wise independent permutations.
In this talk I will discuss some recent results that show that small random reversible circuits compute approximate k-wise independent permutations:
i) We show that a random reversible circuit with ˜O(nk) gates computes a constant-approximate k-wise independent permutation. This result implies a generalization of Shannon's circuit lower bound argument.
ii) We show that a random reversible circuit with ˜O(nk2) layers of 1D-local gates arranged in a brickwork architecture computes a exp(−nk)-approximate k-wise independent permutation; connections to block ciphers exist.
Based on joint works with William Gay (CMU), Lucas Gretta (Berkeley), Nicholas Kocurek (CMU), Ryan O'Donnell (CMU), Angelos Pelecanos (Berkeley).